package com.likou;

import java.util.HashMap;
import java.util.Map;

public class q138 {

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    Map<Node, Node> map = new HashMap<>();
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        if (!map.containsKey(head)) {
            Node newNode = new Node(head.val);
            map.put(head, newNode);
            newNode.next = copyRandomList(head.next);
            newNode.random = copyRandomList(head.random);
        }
        return map.get(head);
    }

//    public Node copyRandomList(Node head) {
//        Map<Node, Node> map = new HashMap<>();
//
//        Node p = head;
//        while (p != null) {
//            Node newNode = new Node(p.val);
//            map.put(p, newNode);
//            p = p.next;
//        }
//
//        p = head;
//        while (p != null) {
//            Node newNode = map.get(p);
//            newNode.next = map.get(p.next);
//            newNode.random = map.get(p.random);
//            p = p.next;
//        }
//
//        return map.get(head);
//
//    }
}
